// 给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。
// 注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。
// 示例 1：

// 输入：arr = [1,0,2,3,0,4,5,0]
// 输出：[1,0,0,2,3,0,0,4]
// 解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]
// 示例 2：

// 输入：arr = [1,2,3]
// 输出：[1,2,3]
// 解释：调用函数后，输入的数组将被修改为：[1,2,3]
 

// 提示：

// 1 <= arr.length <= 104
// 0 <= arr[i] <= 9

/*
 * 思路:1先找到最后一个复写的数
 *     双指针算法：
 *     用cur表示数组首元素，dest表示前一个
 *      即cur=0,dest=-1
 *     (1)判断arr[cur]是否为0，为0则dest+=2,非0则dest++
 *     (2)判断dest是否越界或在数组最后一个元素
 *     (3)cur++
 *      2、边界处理
 *     若dest=arr.length,则说明arr[cur]=0,arr[arr.length-1]=0,
 *      dest-=2, cur--
 *      3、复写元素
 *      判断是否cur>=0，是则进行复写
 *      (1)arr[cur]!=0时
 *      arr[dest--]=arr[cur]
 *      (2)arr[cur]==0时
 *      arr[dest--]=0
 *      arr[dest--]=0
 *      (3)cur--
 * 
 */


 //代码

 class Solution {
    public void duplicateZeros(int[] arr) {
        //
        int cur=0;
        int dest=-1;
        while(cur<arr.length){
            if(arr[cur]!=0){
                dest++;
            }
            else{
                dest+=2;
            }
            if(dest>=arr.length-1){
                break;
            }
            cur++;
        }
        //处理边界情况
        if(dest==arr.length){
            arr[arr.length-1]=0;
            dest-=2;
            cur--;
        }
        //复写
        while(cur>=0){
            if(arr[cur]!=0){
                arr[dest--]=arr[cur--];
            }
            else{
                arr[dest--]=0;
                arr[dest--]=0;
                cur--;
            }
        }
        
    }
}